use rust_practice::graphs::minimize_the_total_price_of_the_trips::Solution;

#[test]
fn minimum_total_price() {
    // 示例 1：
    // 输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
    // 输出：23
    // 解释：
    // 上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
    // 第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
    // 第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
    // 第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
    // 所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。
    assert_eq!(
        Solution::minimum_total_price(
            4,
            vec![vec![0, 1], vec![1, 2], vec![1, 3]],
            vec![2, 2, 10, 6],
            vec![vec![0, 3], vec![2, 1], vec![2, 3]]
        ),
        23
    );

    // 示例 2：
    // 输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
    // 输出：1
    // 解释：
    // 上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
    // 第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
    // 所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。
    assert_eq!(
        Solution::minimum_total_price(2, vec![vec![0, 1]], vec![2, 2], vec![vec![0, 0]]),
        1
    );
}
